/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 *        1
 *      /   \
 *     2     3
 *    / \   / \
 *   4   5 6   7
 */

/**
 * 广度优先，层次遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelTraversal = function(root) {
  let queen = [root];
  let result = [];
  while(queen.length != 0) {
    node = queen.shift();
    result.push(node.val);
    if(node.left) {
      queen.push(node.left);
    }
    if(node.right) {
      queen.push(node.right)
    }
  }
  console.log(result)
};

/**
 * 前序遍历 根左右
 * @param {*} tree 
 */
var preorderTraverse = function(tree) {
  console.log(walk(tree));
  function walk(t) {
    let queen = [t];
    let result = [];
    while(queen.length != 0) {
      let node = queen.shift();
      result.push(node.val);
      if(node.left) {
        result = result.concat(walk(node.left));
      }
      if(node.right) {
        result = result.concat(walk(node.right));
      }
    }
    return result;
  }
}

var midorderTraverse = function(tree) {
  function walk(t) {
    let queen = [t];
    let result = [];
    while(queen.length != 0) {
      let node = queen.shift();
      if(node.left) {
        result = result.concat(walk(node.left));
      }
      result.push(node.val);
      if(node.right) {
        result = result.concat(walk(node.right));
      }
    }
    return result;
  }
  console.log(walk(tree));
}

var afterorderTranverse = function(tree) {
  function walk(t) {
    let queen = [t];
    let result = [];
    while(queen.length != 0) {
      let node = queen.shift();
      if(node.left) {
        result = result.concat(walk(node.left));
      }
      if(node.right) {
        result = result.concat(walk(node.right));
      }
      result.push(node.val);
    }
    return result;
  }
  console.log(walk(tree));
}

var tree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4
    },
    right: {
      val: 5
    }
  },
  right: {
    val: 3,
    left: {
      val: 6
    },
    right: {
      val: 7
    }
  }
}

levelTraversal(tree);
preorderTraverse(tree);
midorderTraverse(tree);
afterorderTranverse(tree);